Linked List, Stack, Queue, এবং Hash Table এর প্রয়োগ

ডেটা স্ট্রাকচারগুলি হল এমন কাঠামো যা ডেটাকে সুশৃঙ্খলভাবে সংরক্ষণ এবং পরিচালনা করতে সাহায্য করে। এগুলি বিভিন্ন প্রোগ্রামিং সমস্যার সমাধানে সহায়ক হয়। এখানে Linked List, Stack, Queue, এবং Hash Table এর সংজ্ঞা এবং তাদের প্রয়োগগুলো আলোচনা করা হলো।

1. Linked List

Linked List একটি ডেটা স্ট্রাকচার যা একাধিক উপাদান (node) নিয়ে গঠিত। প্রতিটি node এ ডেটা এবং পরবর্তী node এর একটি রেফারেন্স থাকে। এটি অ্যারের তুলনায় অনেক বেশি ফ্লেক্সিবল, কারণ এটি ডায়নামিকভাবে মেমোরি বরাদ্দ করতে সক্ষম।

প্রকার:

• Singly Linked List: প্রতিটি node এর পরবর্তী node এর রেফারেন্স থাকে।
• Doubly Linked List: প্রতিটি node এর পরবর্তী এবং পূর্ববর্তী node এর রেফারেন্স থাকে।

প্রয়োগ:

• Dynamic Memory Allocation: Linked list ডায়নামিক মেমোরি বরাদ্দে ব্যবহৃত হয়।
• Implementing Queues and Stacks: Linked list কে স্ট্যাক এবং কিউ সিস্টেম হিসেবে ব্যবহার করা যেতে পারে, যেখানে উপাদানগুলি লিঙ্ক করা থাকে।
• Polynomial Representation: পলিনোমিয়ালগুলির প্রতিনিধিত্ব করতে ব্যবহার করা যায় (যেখানে প্রতিটি node একটি টার্মের প্রতিনিধিত্ব করবে)।
• Graph Representation: গ্রাফের edges গুলি সংরক্ষণ করতে linked list ব্যবহার করা যায়।

উদাহরণ:

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;
    struct Node *next;
};

// Function to insert at the beginning
void insert(struct Node **head, int value) {
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->data = value;
    new_node->next = *head;
    *head = new_node;
}

// Function to display the list
void display(struct Node *head) {
    struct Node *temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node *head = NULL;

    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);

    display(head);  // Output: 30 -> 20 -> 10 -> NULL

    return 0;
}

2. Stack

Stack একটি ডেটা স্ট্রাকচার যা Last In, First Out (LIFO) প্রিন্সিপল অনুসরণ করে। এতে উপাদানগুলি একে একে উপরে চাপানো (push) এবং উপরের উপাদানটি প্রথমে অপসারণ (pop) করা হয়।

প্রয়োগ:

• Function Calls: ফাংশন কলের সিকোয়েন্স ট্র্যাক করার জন্য স্ট্যাক ব্যবহৃত হয়।
• Expression Evaluation: প্যারেন্টেসিস এবং এক্সপ্রেশন ইভ্যালুয়েশনের জন্য স্ট্যাক ব্যবহার করা হয়।
• Undo Mechanism: ডকুমেন্ট বা অ্যাপ্লিকেশনগুলিতে undo/redo ফিচার স্ট্যাক দ্বারা কার্যকরী হয়।
• Backtracking Algorithms: যেমন, ম্যাজল্যাব বা পাজল সলভারের ক্ষেত্রে স্ট্যাক ব্যবহৃত হয়।

উদাহরণ:

#include <stdio.h>
#include <stdlib.h>

#define MAX 5
int stack[MAX];
int top = -1;

// Push operation
void push(int value) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = value;
        printf("Pushed %d\n", value);
    }
}

// Pop operation
int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        return stack[top--];
    }
}

int main() {
    push(10);
    push(20);
    push(30);

    printf("Popped: %d\n", pop());  // Output: 30
    printf("Popped: %d\n", pop());  // Output: 20

    return 0;
}

3. Queue

Queue একটি ডেটা স্ট্রাকচার যা First In, First Out (FIFO) প্রিন্সিপল অনুসরণ করে। এতে উপাদানগুলি একটি প্রান্তে যোগ করা (enqueue) হয় এবং অন্য প্রান্ত থেকে অপসারণ করা (dequeue) হয়।

প্রয়োগ:

• Process Scheduling: অপারেটিং সিস্টেমে প্রক্রিয়া শিডিউলিংয়ের জন্য কিউ ব্যবহৃত হয়।
• Breadth-First Search (BFS): গ্রাফ ট্রাভার্সাল অ্যালগরিদমে কিউ ব্যবহার করা হয়।
• Print Queue: প্রিন্টার শেডিউলিংয়ে কিউ ব্যবহৃত হয়।
• Message Queues: বিভিন্ন কম্পিউটার প্রোগ্রামের মধ্যে বার্তা পাঠানোর জন্য কিউ ব্যবহৃত হয়।

উদাহরণ:

#include <stdio.h>
#include <stdlib.h>

#define MAX 5
int queue[MAX];
int front = -1, rear = -1;

// Enqueue operation
void enqueue(int value) {
    if (rear == MAX - 1) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0;
        queue[++rear] = value;
        printf("Enqueued %d\n", value);
    }
}

// Dequeue operation
int dequeue() {
    if (front == -1) {
        printf("Queue Underflow\n");
        return -1;
    } else {
        int value = queue[front++];
        if (front > rear) front = rear = -1;  // Reset queue if empty
        return value;
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);

    printf("Dequeued: %d\n", dequeue());  // Output: 10
    printf("Dequeued: %d\n", dequeue());  // Output: 20

    return 0;
}

4. Hash Table

Hash Table একটি ডেটা স্ট্রাকচার যা একটি কী-ভ্যালু পেয়ার সংরক্ষণ করে। এটি hash function ব্যবহার করে ইনডেক্স তৈরি করে, যাতে দ্রুত ডেটা অ্যাক্সেস করা যায়। এটি একটি কার্যকরী ডেটা স্ট্রাকচার যা দ্রুত অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশন করে।

প্রয়োগ:

• Database Indexing: ডেটাবেসে ডেটা দ্রুত খোঁজার জন্য।
• Caching: প্রোগ্রামে ডেটা ক্যাশিংয়ের জন্য।
• Unique Data Storage: ডুপ্লিকেট ডেটা এড়ানোর জন্য।
• Associative Arrays: কী-ভ্যালু পেয়ার সংরক্ষণের জন্য।

উদাহরণ:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 10

// Hash function to generate index
int hash(int key) {
    return key % SIZE;
}

void insert(int *hashTable, int key, int value) {
    int index = hash(key);
    hashTable[index] = value;
    printf("Inserted key %d at index %d\n", key, index);
}

int search(int *hashTable, int key) {
    int index = hash(key);
    return hashTable[index];
}

int main() {
    int hashTable[SIZE] = {0};

    insert(hashTable, 1, 100);
    insert(hashTable, 2, 200);
    insert(hashTable, 3, 300);

    printf("Value for key 1: %d\n", search(hashTable, 1));  // Output: 100
    printf("Value for key 2: %d\n", search(hashTable, 2));  // Output: 200

    return 0;
}

এখানে, hash() ফাংশনটি একটি কী নিয়ে তা হ্যাশ করে ইনডেক্স তৈরি করেছে এবং সেই ইনডেক্সে মান সংরক্ষণ করেছে।

সারসংক্ষেপ:

পেয়ার সংরক্ষণ করা। | ডেটাবেস ইনডেক্সিং, ক্যাশিং, ইউনিক ডেটা স্টোরেজ। |

এই ডেটা স্ট্রাকচারগুলি বিভিন্ন ধরনের প্রোগ্রামিং সমস্যার সমাধানে ব্যবহৃত হয়, যেমন ডেটা সংরক্ষণ, দ্রুত অ্যাক্সেস, এবং কার্যকরী সিস্টেম ডিজাইন।